package com.lzy.tricbuild1;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: Tric
 * @Author: Li ZhenYong
 * @description: tric字典树
 * @Date: 2022-04-05 14:54
 * @Version: 1.0
 */
public class Tric {

	private TricNode root = new TricNode('/'); // 存储无意义字符

	// 往Trie树中插入一个字符串
	public void insert(char[] text) { // 例如：hello
		TricNode p = root;
		// 遍历插入的字符串
		for (int i = 0; i < text.length; ++i) {
			// 获取遍历的字符
			int index = text[i] - 'a'; // 找到子节点数组下标
			if (p.children[index] == null) { // 如果对应的节点下标为空，说明当前没有该下标长度前的敏感词。例如现在是hel，则表示没有hel敏感词
				// 赋值
				TricNode newNode = new TricNode(text[i]);
				p.children[index] = newNode;
			}
			p = p.children[index];
		}
		p.isEndingChar = true;  // 当前为最后一个字符串，将标识设置为true
	}

	// 在Trie树中查找一个字符串，存在true,不存在false
	public boolean find(char[] pattern) {
		TricNode p = root;
		for (int i = 0; i < pattern.length; ++i) {  // 进行遍历找到，敏感词最后一个字符
			int index = pattern[i] - 'a';
			if (p.children[index] == null) {
				return false; // 不存在pattern
			}
			p = p.children[index];
		}
		if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
		else return true; // 找到pattern
	}


	// 在Trie树中前缀查找一个字符串,如果存在前缀就返回true，否则返回false
	public boolean findBlur(char[] pattern) {
		TricNode p = root;
		for (int i = 0; i < pattern.length; ++i) {  // 进行遍历找到，敏感词最后一个字符
			int index = pattern[i] - 'a';
			if (p.children[index] == null) {
				return false; // 不存在pattern
			}
			p = p.children[index];
		}
		return true;
	}

	// 获取符合条件的模糊查询字符
	public List<String> getBlur(char[] pattern) {
		TricNode p = root;
		for (int i = 0; i < pattern.length; ++i) {  // 进行遍历找到，敏感词最后一个字符
			int index = pattern[i] - 'a';
			if (p.children[index] == null) {
				return null; // 不存在pattern
			}
			p = p.children[index];
		}
		// pattern是前缀，需要将后面的都找回。
		// p下的所有不为空的节点都需要
		System.out.println(new String(pattern) + " --- " + p.data);

		List<String> result = new ArrayList<>();

		getBlurArr(p,new String(pattern),result);

		return result;
	}

	/**
	 * 获取与前缀匹配的数据
	 * @param p
	 * @param cur
	 * @param ans
	 */
	private void getBlurArr(TricNode p, String cur, List<String> ans) {
		if(null != p && p.isEndingChar) {
			ans.add(cur);
			return;
		}

		TricNode[] children = p.children;

		for (int i = 0; i < children.length; i++) {

			TricNode child = children[i];

			if(children[i] != null) {
				getBlurArr(child, cur+child.data, ans);
			}
		}
	}

	/**
	 *                '/'
	 *          'h'   'e'   'a'
	 *       'e'      'l'   'h'
	 *     'l'        'l'   'e'
	 *   'l' 'o'            'l'
	 * 'o'                  'l'
	 *                      'o'
	 * @param args
	 */
	public static void main(String[] args) {
		Tric tric = new Tric();

		tric.insert("hello".toCharArray());
		tric.insert("heo".toCharArray());
		tric.insert("ello".toCharArray());
		tric.insert("ahello".toCharArray());

		System.out.println(tric.find("h".toCharArray()));  // false
		System.out.println(tric.getBlur("h".toCharArray()));  // [hello, heo]

	}
}
